package cn.chen.数据结构.递归;

/**
 * 8皇后问题：
 * 8*8的棋盘上摆放8个皇后，任意两个皇后不能在同一列、同一行、同一斜线。共有多少种摆法？
 * 我们使用一维数组来表示皇后的摆法：index+1表示皇后所在行，value+1表示皇后所在列
 *
 * */
public class Queen8Recursion {

    private static int max=8;    // 最大皇后数
    private static int[] queen=new int[max];
    public static void main(String[] args){

        check(0);

    }
    // 一行一行递归
    public static void check(int n){    // 参数n就是要摆放的第n个皇后

        if(n==max){ // n=max的时候就代表，这是在摆放下一组了。

            print();
            return;
        }
        // 依次放入皇后，验证是否OK？
        for(int i=0;i<max;i++){ // 从该行的第一列开始放皇后，如果该行的皇后放好了，那么就会进入下一行。如果都好了，那么就会返回到这一行并且将该行的皇后向后移动。

            queen[n]=i; // 从第一列开始放，n是行，也是第n个皇后，i是列，
            if(isOK(n)){    // 是OK的，就需要往下一行走

                check(n+1); // 摆放下一个皇后
            }
            // 不是OK的，就需要跳出本次循环，将皇后放到下一列中，但是这后面没有代码了，所以也不用写continue来跳出本层循环
        }

    }
    // 证明该皇后摆放是否OK？
    public static boolean isOK(int n){

        for(int i=0;i<n;i++){   // 循环遍历该摆法中前面已经摆放了的皇后

            /**
             * queen[i]==queen[n]:就是比较n该皇后是否和前面的皇后在同一列
             * Math.abs(n-i)==Math.abs(queen[n]-queen[i])：比较n该皇后是否和前面的皇后在同一斜线
             * 不会判断是否在同一行，因为index+1代表的就是行，index是不可能重复的。
             * */
            if(queen[i]==queen[n]||Math.abs(n-i)==Math.abs(queen[n]-queen[i])){ // 是否合格

                return false;
            }
        }
        return true;
    }
    // 打印皇后摆放的方法
    public static void  print(){

        // 遍历每一种正确的摆法
        for(int i=0;i<max;i++){

            System.out.print(queen[i]+"\t");
        }
        System.out.println();   // 换行
    }
}
